package greedy;

import java.util.Scanner;

//砌墙，给定每个柱子的高度，求一样高时最少需要移动的次数 
public class QiQiang {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n;
		int[] high;
		while (scanner.hasNext()) {
			n = scanner.nextInt();
			high = new int[n];
			for (int i = 0; i < n; i++) {
				high[i] = scanner.nextInt();
			}
			getMinMove2(high);
		}
		scanner.close();
	}

	//对于0，只能移动1的盒子，对于n，只能移动 n- 1的盒子
	//其他的可以移动两边的
	// 使用贪心算法，如果当前柱子的高度等于平均值，则不移动，否则移动其他柱子的盒子使得
	// 当前柱子的高度等于平均值。
	//每次可以移动多个盒子
	public static void getMinMove(int[] high) {
		int sum = 0, avg = 0; // 平均数
		for (int i = 0; i < high.length; i++) {
			sum += high[i];
		}
		avg = sum / high.length;
		int moveCounts = 0;
		for (int i = 0; i < high.length - 1; i++) {
			// 如果是小于，则将i+1的盒子移至i
			if (high[i] < avg) {
				high[i + 1] = avg - high[i];
				moveCounts++;
			} else if (high[i] > avg) {
				// 如果是大于，那么就直接将多的数目 移至i + 1
				high[i + 1] = high[i + 1] + high[i] - avg;
				moveCounts++;
			}
		}
		System.out.println(moveCounts);
	}
	
	//可以在柱子中随意选择两个进行移动
	//每次只能移动一个盒子
	public static void getMinMove2(int[] high){
		int sum = 0, avg = 0; // 平均数
		for (int i = 0; i < high.length; i++) {
			sum += high[i];
		}
		avg = sum / high.length;
		int moveCounts = 0 ,j = 0;
		for (int i = 0; i < high.length - 1; i++) {
			//想复杂了，这道题就简单的统计所有不等于的即可
			
			// 如果是小于，则将i+1的盒子移至i
			if (high[i] < avg) {
				j = i + 1;
				//遇到一个很奇怪的问题，就是这里这样写竟然会报错！！！！
				//如果我没猜错的话应该是默认为true了，是因为把j++写在后面了吗
//				while((j < high.length) && (high[j++] != avg)){
//					//找到第一个不是avg的
//					high[j] = avg - high[i];
//					System.out.println("j:" + j);
//					moveCounts++;
//				}
				while((j < high.length) && (high[j] != avg)){
					//找到第一个不是avg的
					high[j] = avg - high[i];
					System.out.println("j:" + j);
					moveCounts++;
					j++;
				}
			} else if (high[i] > avg) {
				// 如果是大于，那么就直接将多的数目 移至i + 1
				j = i + 1;
				while(j < high.length && high[j++] != avg){
					//找到第一个不是avg的
					//找到第一个不是avg的
					System.out.println("zzz   j: " + j + "i: " + i +"high.length " + high.length);
					high[j] = high[j] + high[i] - avg;
					moveCounts++;
				}
			}
			
			//方法一： 只计算大于avg的，因为总是将大于的移动至小于的
			if(high[i] > avg){
				moveCounts += high[i] - avg;
			}
			
			//方法2：计算所有不等于avg的，然后将结果除以2即可
			if(high[i] != avg){
				moveCounts += Math.abs(high[i] - avg);
			}
			moveCounts /= 2;
		}
		System.out.println(moveCounts);
	}
}

